<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>课程表问题解析 | 拓扑排序算法可视化</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            line-height: 1.6;
            color: #333;
            background-color: #f8f9fa;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
        }
        .code-block {
            background-color: #282c34;
            border-radius: 8px;
            box-shadow: 0 10px 20px rgba(0,0,0,0.1);
        }
        .solution-card:hover {
            transform: translateY(-5px);
            box-shadow: 0 15px 30px rgba(0,0,0,0.15);
        }
        .mermaid-container {
            background: white;
            border-radius: 12px;
            padding: 24px;
            box-shadow: 0 8px 16px rgba(0,0,0,0.08);
        }
        .step-indicator {
            width: 32px;
            height: 32px;
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
        }
        .divider {
            height: 1px;
            background: linear-gradient(to right, transparent, rgba(0,0,0,0.1), transparent);
        }
    </style>
</head>
<body class="antialiased">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4">
        <div class="container mx-auto max-w-5xl">
            <div class="flex flex-col items-center text-center">
                <h1 class="text-4xl md:text-5xl font-bold mb-6 font-serif">课程安排问题解析</h1>
                <p class="text-xl md:text-2xl max-w-3xl mb-8 opacity-90">
                    拓扑排序算法在课程依赖关系中的应用与可视化
                </p>
                <div class="flex space-x-4">
                    <div class="px-4 py-2 bg-white bg-opacity-20 rounded-full flex items-center">
                        <i class="fas fa-project-diagram mr-2"></i>
                        <span>图论应用</span>
                    </div>
                    <div class="px-4 py-2 bg-white bg-opacity-20 rounded-full flex items-center">
                        <i class="fas fa-code mr-2"></i>
                        <span>算法实现</span>
                    </div>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <div class="container mx-auto max-w-5xl px-4 py-12">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="step-indicator rounded-full flex items-center justify-center text-white mr-4">
                    <span class="font-bold">1</span>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold">问题描述</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6 md:p-8">
                <p class="text-lg mb-4">
                    本学期你需要选修 <span class="font-bold text-purple-600">numCourses</span> 门课程，课程编号从 0 到 numCourses-1。部分课程有先修要求：例如要学习课程 0，必须先完成课程 1，用二元组 <span class="font-bold text-blue-600">[0,1]</span> 表示（0 依赖于 1）。
                </p>
                <p class="text-lg">
                    给定课程总数和先修课程要求，判断是否可能完成所有课程的学习。例如：
                </p>
                <div class="mt-4 bg-gray-50 p-4 rounded-lg border-l-4 border-purple-500">
                    <p class="font-mono text-gray-700">
                        输入: numCourses = 2, prerequisites = [[1,0]]<br>
                        表示总共 2 门课，学习课程 1 前需要完成课程 0<br>
                        输出: true (可以先学 0，再学 1)
                    </p>
                </div>
                <div class="mt-6">
                    <div class="mermaid-container">
                        <div class="mermaid">
                            graph LR
                            0 --> 1
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Core Concepts -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="step-indicator rounded-full flex items-center justify-center text-white mr-4">
                    <span class="font-bold">2</span>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold">核心考点与算法</h2>
            </div>
            
            <div class="grid grid-cols-1 md:grid-cols-2 gap-6">
                <div class="solution-card bg-white rounded-xl shadow-md p-6 transition-all duration-300">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 bg-blue-100 rounded-full flex items-center justify-center text-blue-600 mr-3">
                            <i class="fas fa-sitemap"></i>
                        </div>
                        <h3 class="text-xl font-bold">拓扑排序</h3>
                    </div>
                    <p class="text-gray-700 mb-4">
                        将课程依赖关系建模为有向图，通过拓扑排序检测图中是否存在环。若无环，则存在可行的学习顺序。
                    </p>
                    <div class="bg-blue-50 p-3 rounded-lg">
                        <p class="text-sm text-blue-800">
                            <i class="fas fa-lightbulb mr-1"></i>
                            关键思想：课程依赖关系构成有向无环图(DAG)时才可能有解
                        </p>
                    </div>
                </div>
                
                <div class="solution-card bg-white rounded-xl shadow-md p-6 transition-all duration-300">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 bg-purple-100 rounded-full flex items-center justify-center text-purple-600 mr-3">
                            <i class="fas fa-braille"></i>
                        </div>
                        <h3 class="text-xl font-bold">两种实现方法</h3>
                    </div>
                    <ul class="space-y-2 text-gray-700">
                        <li class="flex items-start">
                            <i class="fas fa-circle text-xs mt-1.5 mr-2 text-blue-500"></i>
                            <span><strong>DFS法：</strong>检测图中是否有环，若无环则可完成</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-circle text-xs mt-1.5 mr-2 text-purple-500"></i>
                            <span><strong>BFS法：</strong>计算入度，从入度为0的节点开始拓扑排序</span>
                        </li>
                    </ul>
                </div>
            </div>
        </section>

        <!-- Visualization -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="step-indicator rounded-full flex items-center justify-center text-white mr-4">
                    <span class="font-bold">3</span>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold">算法可视化</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6 md:p-8">
                <div class="mermaid-container mb-6">
                    <div class="mermaid">
                        graph TD
                        A[开始] --> B[构建邻接表和入度数组]
                        B --> C{是否有入度为0的节点?}
                        C -->|是| D[将其加入队列]
                        C -->|否| E[存在环，返回false]
                        D --> F[处理队列中的节点]
                        F --> G[减少相邻节点入度]
                        G --> H{邻接入度变为0?}
                        H -->|是| I[加入队列]
                        H -->|否| J[继续处理]
                        I --> F
                        F --> K{是否处理所有节点?}
                        K -->|是| L[返回true]
                        K -->|否| F
                    </div>
                </div>
                
                <div class="grid grid-cols-1 md:grid-cols-3 gap-4 mt-6">
                    <div class="bg-blue-50 p-4 rounded-lg">
                        <div class="text-blue-600 font-bold mb-2">时间复杂度</div>
                        <p class="text-sm">O(V + E)</p>
                        <p class="text-xs text-gray-600 mt-1">V: 课程数量，E: 依赖关系数量</p>
                    </div>
                    <div class="bg-purple-50 p-4 rounded-lg">
                        <div class="text-purple-600 font-bold mb-2">空间复杂度</div>
                        <p class="text-sm">O(V)</p>
                        <p class="text-xs text-gray-600 mt-1">存储邻接表和入度数组</p>
                    </div>
                    <div class="bg-green-50 p-4 rounded-lg">
                        <div class="text-green-600 font-bold mb-2">适用场景</div>
                        <p class="text-sm">任务调度、课程安排、工作流管理</p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Solution Code -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <div class="step-indicator rounded-full flex items-center justify-center text-white mr-4">
                    <span class="font-bold">4</span>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold">BFS解法实现</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md overflow-hidden">
                <div class="bg-gray-800 px-4 py-3 flex items-center">
                    <div class="flex space-x-2 mr-4">
                        <div class="w-3 h-3 rounded-full bg-red-500"></div>
                        <div class="w-3 h-3 rounded-full bg-yellow-500"></div>
                        <div class="w-3 h-3 rounded-full bg-green-500"></div>
                    </div>
                    <div class="text-gray-300 text-sm">canFinish.py</div>
                </div>
                <div class="code-block p-4 md:p-6 overflow-x-auto">
                    <pre class="text-gray-200 font-mono text-sm md:text-base">
<span class="text-pink-400">def</span> <span class="text-yellow-300">canFinish</span>(numCourses, prerequisites):
    <span class="text-pink-400">from</span> collections <span class="text-pink-400">import</span> defaultdict, deque
    graph = defaultdict(list)
    indegree = [<span class="text-blue-400">0</span>] * numCourses
    <span class="text-pink-400">for</span> dest, src <span class="text-pink-400">in</span> prerequisites:
        graph[src].append(dest)
        indegree[dest] += <span class="text-blue-400">1</span>
    
    queue = deque([i <span class="text-pink-400">for</span> i <span class="text-pink-400">in</span> range(numCourses) <span class="text-pink-400">if</span> indegree[i] == <span class="text-blue-400">0</span>])
    count = <span class="text-blue-400">0</span>
    <span class="text-pink-400">while</span> queue:
        node = queue.popleft()
        count += <span class="text-blue-400">1</span>
        <span class="text-pink-400">for</span> neighbor <span class="text-pink-400">in</span> graph[node]:
            indegree[neighbor] -= <span class="text-blue-400">1</span>
            <span class="text-pink-400">if</span> indegree[neighbor] == <span class="text-blue-400">0</span>:
                queue.append(neighbor)
    <span class="text-pink-400">return</span> count == numCourses</pre>
                </div>
            </div>
        </section>

        <!-- Explanation -->
        <section>
            <div class="flex items-center mb-6">
                <div class="step-indicator rounded-full flex items-center justify-center text-white mr-4">
                    <span class="font-bold">5</span>
                </div>
                <h2 class="text-2xl md:text-3xl font-bold">代码解析</h2>
            </div>
            
            <div class="bg-white rounded-xl shadow-md p-6 md:p-8">
                <div class="space-y-6">
                    <div class="flex items-start">
                        <div class="flex-shrink-0 h-8 w-8 rounded-full bg-indigo-100 flex items-center justify-center text-indigo-600 mr-4">
                            <i class="fas fa-arrow-right"></i>
                        </div>
                        <div>
                            <h4 class="font-bold text-lg mb-2">1. 数据结构初始化</h4>
                            <p class="text-gray-700">使用<code class="bg-gray-100 px-2 py-1 rounded">defaultdict</code>建立邻接表表示图，<code class="bg-gray-100 px-2 py-1 rounded">indegree</code>数组记录每门课程的入度(依赖课程数)</p>
                        </div>
                    </div>
                    
                    <div class="divider my-4"></div>
                    
                    <div class="flex items-start">
                        <div class="flex-shrink-0 h-8 w-8 rounded-full bg-green-100 flex items-center justify-center text-green-600 mr-4">
                            <i class="fas fa-project-diagram"></i>
                        </div>
                        <div>
                            <h4 class="font-bold text-lg mb-2">2. 构建图结构</h4>
                            <p class="text-gray-700">遍历<code class="bg-gray-100 px-2 py-1 rounded">prerequisites</code>数组，填充邻接表和入度数组，建立课程间的依赖关系</p>
                        </div>
                    </div>
                    
                    <div class="divider my-4"></div>
                    
                    <div class="flex items-start">
                        <div class="flex-shrink-0 h-8 w-8 rounded-full bg-blue-100 flex items-center justify-center text-blue-600 mr-4">
                            <i class="fas fa-search"></i>
                        </div>
                        <div>
                            <h4 class="font-bold text-lg mb-2">3. 拓扑排序处理</h4>
                            <p class="text-gray-700">将所有入度为0的课程加入队列，依次处理并"删除"它们，减少依赖它们的课程的入度。如果新入度为0则加入队列</p>
                        </div>
                    </div>
                    
                    <div class="divider my-4"></div>
                    
                    <div class="flex items-start">
                        <div class="flex-shrink-0 h-8 w-8 rounded-full bg-purple-100 flex items-center justify-center text-purple-600 mr-4">
                            <i class="fas fa-check-circle"></i>
                        </div>
                        <div>
                            <h4 class="font-bold text-lg mb-2">4. 结果验证</h4>
                            <p class="text-gray-700">如果处理过的课程数等于总课程数，说明可以完成所有课程(无环)；否则存在循环依赖无法完成</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>
    </div>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>